package com.example.designpatterns.strategy.sorting;

import com.example.designpatterns.strategy.Strategy;
import java.util.Arrays;

/**
 * 基数排序策略 - 使用基数排序算法实现排序
 * 时间复杂度：O(d*(n+k))，其中d是最大数字的位数，k是基数（通常为10）
 * 空间复杂度：O(n+k)
 * 稳定性：稳定
 * 适用于整数或字符串排序，尤其是位数较小且分布均匀的数据
 */
public class RadixSortStrategy implements Strategy<int[], int[]> {
    
    @Override
    public int[] execute(int[] input) {
        if (input == null || input.length <= 1) {
            return input;
        }
        
        // 创建数组副本，不修改原始数据
        int[] array = Arrays.copyOf(input, input.length);
        
        // 找出最大值，确定最大位数
        int max = Arrays.stream(array).max().getAsInt();
        
        // 对每个位进行计数排序
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSortByDigit(array, exp);
        }
        
        return array;
    }
    
    /**
     * 根据特定位数对数组进行计数排序
     * @param array 待排序数组
     * @param exp 当前处理的位数（1表示个位，10表示十位，依此类推）
     */
    private void countingSortByDigit(int[] array, int exp) {
        int n = array.length;
        int[] output = new int[n]; // 输出数组
        int[] count = new int[10]; // 计数数组，对于十进制数字，范围是0-9
        
        // 初始化计数数组
        Arrays.fill(count, 0);
        
        // 统计当前位出现的次数
        for (int i = 0; i < n; i++) {
            count[(array[i] / exp) % 10]++;
        }
        
        // 计算累积计数，确定元素的实际位置
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }
        
        // 从后向前遍历，构建输出数组
        for (int i = n - 1; i >= 0; i--) {
            int digit = (array[i] / exp) % 10;
            output[count[digit] - 1] = array[i];
            count[digit]--;
        }
        
        // 将排序结果复制回原数组
        System.arraycopy(output, 0, array, 0, n);
    }
} 